//
//Copyright GX. Yuan
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//   http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

/**
 * @file net.go
 * @brief Leetcode 剑指Offer 第二版
 * @details 剑指 Offer 37. 序列化二叉树
 * @author GX. Yuan  any question please send mail to yuanguanxu@qq.com
 * @date 2021-6-28
 * @version V1.0
 * @attention 硬件平台: windows 10 家庭版
 * SDK版本：Go 1.16.5
 * IDE版本：GoLand 2020.2.3
 */

class Codec {
public:
    void rserialize(TreeNode* root, string& str) {
        if (root == nullptr) {
            str += "None,";
        } else {
            str += to_string(root->val) + ",";
            rserialize(root->left, str);
            rserialize(root->right, str);
        }
    }

    string serialize(TreeNode* root) {
        string ret;
        rserialize(root, ret);
        return ret;
    }

    TreeNode* rdeserialize(list<string>& dataArray) {
        if (dataArray.front() == "None") {
            dataArray.erase(dataArray.begin()); // 删除这个数值
            return nullptr;
        }

        TreeNode* root = new TreeNode(stoi(dataArray.front()));
        dataArray.erase(dataArray.begin()); // 删除这个数值.进入到下一个位置的处理; 由于存在NULL的判断，更具顺序和none的位置，可以恢复数据。
        root->left = rdeserialize(dataArray);
        root->right = rdeserialize(dataArray);
        return root;
    }

    TreeNode* deserialize(string data) {
        list<string> dataArray;
        string str;
        for (auto& ch : data) {
            if (ch == ',') {
                dataArray.push_back(str);
                str.clear();
            } else {
                str.push_back(ch);
            }
        }
        if (!str.empty()) {
            dataArray.push_back(str);
            str.clear();
        }
        return rdeserialize(dataArray);
    }
};

// 思路
//  1. 关于二叉树的遍历取值
//  在节点的序列化的过程中，遇到的null的位置的时候，需要将他None 记录下来；
//  2. 关于二叉树的前序遍历重建；

//  重建的处理方式是
//  将NULL 中的位置，记录为none这样标记终止位置，进行恢复。
//  这一题的思路上，是没有难度，但是，在使用是唯一问题的是:关于算法的NULL的处理和恢复
